public class ListNodeTest {
    int val;
    ListNode next;

    ListNode head;
    /**
     * 计算节点个数
     * @param head
     * @return
     */
    public int size(ListNode head){
        ListNode cur=head;
        int count=0;

        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    /**
     * 判断两链表是否有交点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA=size(headA);
        int lenB=size(headB);
        ListNode curA=headA;
        ListNode curB=headB;

        if(lenA>lenB){
            while(lenA-lenB!=0){
                curA=curA.next;
                lenA--;
            }
        }else{
            while(lenB-lenA!=0){
                curB=curB.next;
                lenB--;
            }
        }
        while(curA!=null&&curB!=null){
            if(curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;

        }
        return null;

    }

    /**
     * 判断是否为回文链表
     * @return
     */
    public boolean chkPalindrome() {
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;

        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;

        }
        return true;
    }
    /**
     * 小于x在前，大于x在后，合成新链表
     * @param pHead
     * @param x
     * @return
     */
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur=pHead;
        ListNode bhead=null;
        ListNode bcur=null;
        ListNode ahead=null;
        ListNode acur=null;
        while(cur!=null){
            if(cur.val<x){
                if(bhead==null){
                    bhead=cur;
                    bcur=cur;
                }else{
                    bcur.next=cur;
                    bcur=bcur.next;
                }
                cur=cur.next;
            }else{
                if(ahead==null){
                    ahead=cur;
                    acur=cur;
                }else{
                    acur.next=cur;
                    acur=acur.next;
                }
                cur=cur.next;
            }
        }
        if(bcur==null){
            return ahead;
        }
        bcur.next=ahead;

        if(ahead!=null){
            acur.next=null;
        }
        return bhead;
    }
    /**
     * 合并两个升序链表
     * @param head1
     * @param head2
     * @return
     */
    public ListNode mergeTwoLists(ListNode head1,ListNode head2){
        ListNode nhead=new ListNode();
        ListNode cur=nhead;
        while(head1!=null&&head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                cur=cur.next;
                head1=head1.next;
            }else{
                cur.next=head2;
                cur=cur.next;
                head2=head2.next;
            }
        }
        if(head2==null){
            while(head1!=null){
                cur.next=head1;
                cur=cur.next;
                head1=head1.next;
            }

        }else{
            while(head2!=null){
                cur.next=head2;
                cur=cur.next;
                head2=head2.next;
            }
        }
        return nhead;

    }
}

